package william.xor;

/**
 * @author ZhangShenao
 * @date 2024/1/19
 * @description <a href="https://leetcode.cn/problems/single-number-iii/description/">...</a>
 */
public class Leetcode206_只出现一次的数字3 {
    /**
     * 基于异或操作的性质
     * Step1: 遍历数组，依次对每一个元素进行异或操作。出现了偶数次的数字异或后会互相抵消，最后得到的结果就是两个数异或。
     * Step2: 提取出异或结果的右侧的第一个1，说明这两个数在该位不相等。因此可以基于这个条件，将整个数组划分成两部分：该位=1的，和该位=0的，目标的两个元素分属于两个组中。
     * Step3: 再次遍历数组，仅取出该位为1的数，依次进行异或，最终得到的结果就是其中一个数。
     * Step4: 最后将两个异或的结果再次异或，得到另一个数。
     */
    public int[] singleNumber(int[] nums) {
        //边界条件校验
        if (nums == null || nums.length < 2) {
            return new int[0];
        }

        //首先将数组运算逐个异或,得到的结果就是两个出现奇数次元素的异或结果
        int xor = 0;
        for (int n : nums) {
            xor ^= n;
        }

        //提取出异或结果右侧的第一个1,说明两个元素在该位不相等
        int rightFirstOne = xor & (~xor + 1);

        //基于右侧的第一个1,将整个数组的元素分成两组:该位为1的,和该位为0的
        //再次遍历数组,仅取出该位为1的元素,依次进行异或,出现偶数次的元素会互相抵消,最终得到的结果即为其中的一个元素
        int firstNum = 0;
        for (int n : nums) {
            if ((n & rightFirstOne) != 0) {
                firstNum ^= n;
            }
        }

        //将其中一个数与异或结果再次异或,即得到另一个数
        int secondNum = xor ^ firstNum;

        //返回两个元素
        return new int[]{firstNum, secondNum};
    }
}
